package 热题100.二叉树.二叉树的层序遍历_102_中等;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import 热题100.二叉树.二叉树的中序遍历_94_简单.Solution.TreeNode;
/*
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：
输入：root = [1]
输出：[[1]]

示例 3：
输入：root = []
输出：[]

提示：
树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

思路：
    采用队列的方法
    1. 先放根节点
    2. 如果队列不为空（判断），先查看队列长度len，以区分队列的当前层节点和下一层节点
    3. 用while循环对队列中的元素处理（while len > 0），并从队列拿出节点
    4. 将它的左节点和右节点放入队列直到len=0
    5. 将这一次的结果存入答案队列。
    必须用while循环，因为同一层的节点会在同一时刻全放进去，查看队列长度，遍历出来记录就行，记录的同时
    将下次的子节点也放入队列，互不影响。
* */
public class Solution {
    public static void main(String[] args) {
        TreeNode node3 = new TreeNode(3, null, null);
        TreeNode node2 = new TreeNode(2, node3, null);
        TreeNode root = new TreeNode(1, null, node2);
        List<List<Integer>> ans = levelOrder(root);
        for (List<Integer> p: ans){
            for (int q : p){
                System.out.print(q + " ");
            }
            System.out.println();
        }
    }
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        // 队列存的当前层和下一层的节点
        Deque<TreeNode> deque = new ArrayDeque<>();
        if (root == null){
            return null;
        }
        // 先将根节点放进队列
        deque.offer(root);
        // 队列不为空就继续执行
        while (!deque.isEmpty()){
            // 当前队列存的就是一开始每一层的节点
            List<Integer> levelList = new ArrayList<>();
            int len = deque.size();
            // 那么就根据当前队列的长度来遍历
            while (len > 0){
                TreeNode node = deque.poll();
                // 将节点存入当前层的链表
                levelList.add(node.val);
                if (node.left != null) {
                    // 添加下一层的节点到队列
                    deque.offer(node.left);
                }
                if (node.right != null){
                    deque.offer(node.right);
                }
                len --;
            }
            ans.add(levelList);
        }
        return ans;
    }
}
